// 前缀和 + 动态规划 + 哈希表
// 本质上是一个动态规划的思想，关键步骤如下：
// 1.确定状态表示
// 2.推导动态转移方程
// 3.初始化
// 4.确定填表顺序
// 5.确定返回值

// 例题 6：
//给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的非空 子数组 的数目。
// 子数组 是数组中 连续 的部分。
//
//        示例 1：
//
//        输入：nums = [4,5,0,-2,-3,1], k = 5
//        输出：7
//        解释：
//        有 7 个子数组满足其元素之和可被 k = 5 整除：
//        [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
//        示例 2:
//
//        输入: nums = [5], k = 9
//        输出: 0
//
//
//        提示:
//
//        1 <= nums.length <= 3 * 104
//        -104 <= nums[i] <= 104
//        2 <= k <= 104

// 解题思路：
// 本题乍一看是一个找子数组个数的题目，首先就会想到用滑动窗口的办法
// 再仔细一看，发现数组里面的数值有正有负，数据本身不具备单调性，因此无法用滑动窗口解题
// 进而利用动态规划的思想进行解题，首先需要定义状态表示 dp[i]
// dp[i]：以 i 位置为结尾和为 k 的子数组的个数，定义完状态表示后，我们发现不好推导状态转移方程
// 原因是 dp[i] 和 dp[i - 1] 没有直接的关系，dp[i] 和前面的所有 dp[j] 有关系
// 因此想到使用前缀和的办法：dp[i] = 前缀和对 k 取余为 (sum % k + k) % k 的子数组的个数，这也同时符合“正难则反”的思想
// 统计个数最好的数据结构还是哈希表，因为哈希表查询的时间复杂度为 O(1)
// 因此，每动态规划一个 dp[i]，就需要把它相应的前缀和放进哈希表
// ret += dp[i]，即 ret += hash.getOrDefault((sum % k + k) % k, 0);

// 本题的难点有两个：一个是同余定理，另外一个是 Java 中负数取余的修正方法
// 同余定理：(a + b) % p = a % p + b % p
// Java 中的负数取余修正：如果 a < 0, 为了取完模得到正数，采用 (a % p + p) % p
// 如果 i 位置结尾的某个子数组能整除 k，那么 (sum - x) % k == 0，即 sum % k = x % k，x 是刨除子数组的前缀和
// 即只要找到前缀和对 k 取余后值为 sum % k 的元素个数，就是以 i 位置结尾的能被 k 整除的子数组的个数

import java.util.HashMap;
import java.util.Map;

public class SubarraysDivByK {
    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer, Integer> hash = new HashMap<>();
        hash.put(0, 1);
        int sum = 0;
        int ret = 0;
        for(int x : nums){
            sum += x;
            int tmp = (sum % k + k) % k;
            ret += hash.getOrDefault(tmp, 0);
            hash.put(tmp, hash.getOrDefault(tmp, 0) + 1);
        }
        return ret;
    }
}
